package leetcode.weekly.week341;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	List<List<Integer>> nexts;
	int[] cnts;
	int[] p1;
	int[] p2;
	int[] price;
	int cost[];

	public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
		nexts = new ArrayList<>();
		this.price = price;
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] e : edges) {
			int a = e[0], b = e[1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		int len = trips.length;
		int[] parents = new int[len];
		int[] froms = new int[len];
		for (int i = 0; i < len; i++) {
			int[] t = trips[i];
			int a = t[0], b = t[1];
			int[] cur = find(-1, 0, a, b);
			parents[i] = cur[1];
			froms[i] = cur[2];
		}
		cnts = new int[n];
		for (int i = 0; i < len; i++) {
			int[] t = trips[i];
			int a = t[0], b = t[1];
			query(froms[i], parents[i], a, b);
		}
		cost = new int[n];
		for (int i = 0; i < n; i++) {
			cost[i] = cnts[i] * price[i];
		}
		Integer dp[][][] = new Integer[50][50][2];
		int ans1 = count(-1, 0, 1, dp);// 能
		Integer dp1[][][] = new Integer[50][50][2];
		int ans2 = count(-1, 0, 0, dp1);// 0 不能
		return Math.min(ans1, ans2);
	}

	private int count(int from, int p, int flag, Integer[][][] dp) {
		if (nexts.get(p).size() == 1 && nexts.get(p).get(0) == from) {
			return flag == 1 ? this.cost[p] / 2 : this.cost[p];
		}
		if (from != -1 && dp[from][p][flag] != null) {
			return dp[from][p][flag];
		}
		int ans = Integer.MAX_VALUE;
		if (flag == 1) {
			int cur = 0;
			for (int next : nexts.get(p)) {
				if (next != from) {
					cur += count(p, next, 0, dp);
				}
			}
			ans = cur + (this.cost[p] >> 1);
		}
		int cur = 0;
		for (int next : nexts.get(p)) {
			if (next != from) {
				cur += count(p, next, 1, dp);
			}
		}
		ans = Math.min(ans, cur + this.cost[p]);
		if (from != -1)
			dp[from][p][flag] = ans;
		return ans;
	}

	private boolean query(int from, int p, int a, int b) {
		if (nexts.get(p).size() == 1 && nexts.get(p).get(0) == from) {
			if (p == a || p == b) {
				cnts[p]++;
				return true;
			}
			return false;
		}
		boolean add = false;
		if (p == a || p == b) {
			cnts[p]++;
			add = true;
		}
		for (int next : nexts.get(p)) {
			if (next != from) {
				boolean cur = query(p, next, a, b);
				if (cur && !add) {
					cnts[p]++;
					add = true;
				}
			}
		}
		return add;
	}

	private int[] find(int from, int p, int a, int b) {
		if (nexts.get(p).size() == 1 && nexts.get(p).get(0) == from) {
			if (p == a && p == b) {
				return new int[] { 2, p, from };
			}
			return new int[] { (p == a || p == b ? 1 : 0), -1 };
		}
		if (p == a && p == b) {
			return new int[] { 2, p, from };
		}
		boolean root = p == a || p == b;
		int have = root ? 1 : 0;
		for (int next : nexts.get(p)) {
			if (next != from) {
				int[] cur = find(p, next, a, b);
				if (cur[0] == 2) {
					return cur;
				} else if (cur[0] == 1) {
					have++;
					if (have == 2) {
						return new int[] { 2, p, from };
					}
				}
			}
		}
		return new int[] { have, -1, -1 };
	}
}
